from typing import Optional

from python.mypackage import TreeNode


class Solution:

    """
     方法： 通过栈实现中序遍历，找到第k小的元素
     
     Args:
         root: Optional[TreeNode] - 二叉树的根节点
         k: int - 需要找到第k小的元素
     
     Returns:
         int: 第k小的元素的值
     
     Time: O(n) - 其中n是二叉树的节点数，二叉树的每个节点最多被访问一次，因此时间复杂度为O(n)
     
     Space: O(n)，其中n是二叉树的节点个数。栈最多存储n个节点，因此需要额外的O(n)的空间
     """
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

    """
     方法： 通过递归实现中序遍历，找到第k小的元素
     
     Args:
         root: Optional[TreeNode] - 二叉树的根节点
         k: int - 需要找到第k小的元素
     
     Returns:
         int: 第k小的元素的值
     
     Time: O(n) - 其中n是二叉树的节点数，每个节点只被访问一次
     
     Space: O(h) - 其中h是二叉树的高度，用于存储递归调用栈
     """
    def kthSmallest1(self, root: Optional[TreeNode], k: int) -> int:
        ans = 0
        def dfs(node: Optional[TreeNode]) -> None:
            if node is None:
                return
            dfs(node.left)
            nonlocal k, ans
            k -= 1
            if k == 0:
                ans = node.val
            dfs(node.right)
        dfs(root)
        return ans;